/*
Date:20210505 9:38AM
key:像反转链表一样，带着头指针进入到末尾，在递归回来的时候每次比较是否相等，并通过额外变量记录有无先不等的情况。
    注意越过中间仍是二者相等

    快慢指针反转后半段也可以
 */
class Solution {
public:
    ListNode* f(ListNode* head,ListNode* &head2,bool&flag)
    {
        if(head->next!=nullptr)
        {
            ListNode*p=f(head->next,head2,flag);
            if(head2->val!=p->val){flag=0;}
            //ji
            head2=head2->next;
            //
            return head;
        }
        else
        {
            if(head2->val!=head->val){flag=0;}
            return head;
        }
    }
    bool isPalindrome(ListNode* head) 
    {
        bool flag=1;
        if(head==nullptr){return 1;}
        int count=0;
        ListNode*p=head;
        // while(p!=nullptr)
        // {
        //     count++;
        //     p=p->next;
        // }
        // if(count<3){return 1;}
        // else
        {
                    f(head,head,flag);
        return flag;
        }

    }
};